This notes are problem-centered: we introduce a problem and then the theory to efficiently solve it.
Use at Your Own Risk.
For each possible subarray we compute the sum and store the maximum
brute_force(a[])
n = a.length()
max = Integer.MIN_VALUE
for i = 0 to n
sum = 0
for j = i to n
sum += a[j]
if sum > max
max = sum
return max
Kadane's algorithm is based on two properties of the subarray with maximum sum:
To solve the problem we use Kadane's algorithm:
kadane_algorithm(a[])
n = a.length()
max = Integer.MIN_VALUE
sum = 0
for i = 0 to n
if sum > 0 // property 1)
sum += arr[i]
else // property 2)
sum = arr[i]
max = Math.max(sum, max)
return max
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Traverse every array element and find the highest bars on the left and right sides.
Take the smaller of two heights.
The difference between the smaller height and the height of the current element is the amount of water that can be stored in this array element.
The point is to think locally, not globally.
We can compute the left and right leaders.
An element of array is a right leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader.
Given the array
Now, how many units of water we can find on top of the cell
The minimum height between the left and right leader of the current position minus
The idea is taken from the Precomputation solution, where we only use two variables to store the currently "meaningful" leaders.
We take two pointers, left and right and we initialize left to 0 and right to the last index n-1.
We also create two variables, left_max and right_max, they represent the maximum left/right height seen so far.
Since left is the first left_max is 0, same for right_max.
This is intuitive: we can't store water in the first and last column.
Now we iterate, as long left < right.
We have to decide which pointer we have to shift: we shift the pointer that has smaller height value:
heights[left] < heights[right] we shift leftright otherwiseNow, if we have that heights[left] > left_max we can't store any water over the position pointed by left, it would fall as left_max is not high enough.
Otherwise we compute the amount of water stored in left, as always with left_max - heights[left]. Then we finally shift left by 1.
The reasoning with the right pointer is the same.
The following pseudo-code solves the problem
max_water(heights[])
n = heights.length()
result = 0
left = 0
right = n-1
left_max = 0 // max height seen by "left" so far
right_max = 0 // max height seen by "right" so far
while left < right
if heights[left] < heights[right] // shift "left"
if heights[left] > left_max
left_max = heigths[left] // cant store water
else
result += left_max - heights[left]
left += 1
else // shift right
if heights[right] > right_max
right_max = heights[right] // cant store water
else
result += right_max - heights[right]
right -= 1
return result
To solve this problem we use Binary Search.
We start by giving the basics of this technique.
An efficient algorithm that searches for a given key within a sorted array of items.
Binary search repeatedly divides the search range in half until the target element is found or the search range becomes empty, resulting in a time complexity of
Binary search is a technique that falls under the umbrella of the divide-and-conquer paradigm, that tackles a complex problem by breaking it down into smaller, more manageable subproblems of the same type:
Considering the binary search, we have:
It is also important to observe that when there are multiple occurrences of the searched key, the function returns the position of the first encountered occurrence, not necessarily the first occurrence in the vector.
However, it is often very useful to report the position of the first (or last) occurrence of the searched key.
We can obtain this behavior with the following pseudo-implementation.
binary_search(a[], target)
n = a.length()
low = 0
high = n - 1
answer = -1
while low < high
// (low + high)/2 might overflow if (high+low) is very big
middle = low + (high - low) / 2
if a[middle] == target
answer = middle
high = middle
else if a[middle] < target
low = middle
else
high = middle
return answer
In this implementation, when a match is found, we do not immediately return its position. Instead, we update the answer variable and set high to the position of this occurrence.
This way, we continue the search in the first half of the array, seeking additional occurrences of the key.
If there are more matches, answer will be further updated with smaller positions.
Consider a problem where all the possible candidate answers are restricted to a range of values between certain low and high possible answers.
In other words, any candidate answer [low, high].
We also have a boolean predicate pred defined on the candidate answers that tells us if an answer is good or bad for our aims.
Our goal is to find the largest good answer.
When no assumption are made about the predicate, we cannot do better than evaluating the predicate on all possible answers.
Hence, the number of times we evaluate the predicate is
On the other hand, if the predicate is monotone, we can binary search the answer to find it with
A predicate is said to be monotone if the truth value of a predicate is true for one combination of inputs, it will remain true if any of those inputs are increased (or remain the same). Similarly, if the truth value is false for one combination, it will remain false or become true if any of the inputs are increased (or remain the same).
The following pseudo-code clarifies the concept:
rangeBS(pred, low, high)
low = low;
high = high;
answer;
while low < high
mid = low + (high-low) / 2
if pred(mid) == true
answer = mid
low = mid + 1 // we want the largest good answer
else
high = mid
return answer
We can use the previous problem to compute the square root.
We are given a non-negative integer
The possible answers are in
We can find the result simply by doing rangeBS(p, 0, v+1)
We have a sequence of
We aim to find
If a certain distance is feasible (i.e., there exists a selection of points at that distance), then any smaller distance is also feasible.
Thus the feasibility is a monotone boolean predicate that we can use to binary search the answer.
As the candidate answers range from
Whats the cost of evaluating the predicate?
We first sort the intervals.
Now we can evaluate any candidate distance
First we select the left extreme of the first interval as the first point. Then, we move over the intervals and we choose greedily the first point, which is at a distance at least
Thus an evaluation of the predicate takes
The total running time is
The pseudo-implementation greatly clarifies the process:
pred(intervals, distance, c)
// the first point is the start of the first interval
lastSelected = intervals[0].start
counter = 1
// for every interval in intervals
for interval in intervals
// we select as many points as we can in every interval
while Math.max(lastSelected + distance, interval.start) <= interval.end
lastSelected = Math.max(lastSelected + distance, interval.start)
counter++
return counter >= c
socialDistancing(intervals, c)
// l is the maximum length of an interval
if l < c
return -1 // there is no solution
// sort the intervals
intervals.sort()
rangeBS(1, l+1, pred)
We can use the binary search philosophy to solve the problem.
We compute the middle of the array.
If the element in the middle is smaller than its right neighbor than the right neighbor could be a leader, and we do low = mid + 1 to proceed the search in the right side of the array.
Otherwise we do the opposite.
peak_elements(a[])
n = a.length()
low = 0
right = n - 1
while low < high
mid = low + (high - low) / 2
if a[mid] < a[mid + 1]
low = mid + 1
else
right = mid
return low
This solution works because a leader is guaranteed to be found (as a last resource, in the first or last element of the array).
The beauty of this solution is that it naturally covers all the strange cases.
It would be tempting to write something like
if a[mid] > a[mid+1] && a[mid] > a[mid-1]
return mid
but that requires to cover many edge cases (array of size 1, 2, if mid is
Find the maximum possible sum from one leaf node to another.
To solve this problem we need to use a tree traversal.
Fist we go back and give the basics.
Tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once.
Such traversals are classified by the order in which the nodes are visited.
Traversing a tree involves iterating over all nodes in some manner.
Because from a given node there is more than one possible next node some nodes must be deferred, aka stored, in some way for later visiting.
This is often done via a stack (LIFO) or queue (FIFO).
As a tree is a recursively defined data structure, traversal can be defined by recursion.
In these cases the deferred nodes are stored implicitly in the call stack.
Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue.
In depth-first search (DFS), the search tree is deepened as much as possible before going to the next sibling.
To traverse binary trees with depth-first search, perform the following operations at each node:
The choice of exactly one color determines exactly one visit of a node as described below.
Complexity Analysis:
The preorder traversal is a topologically sorted one, because the parent node is processed before any of its child nodes is done.
procedure postorder(node)
if node = null
return
postorder(node.left)
postorder(node.right)
visit(node)
In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.
A simple solution is to traverse the tree and do following for every traversed node
Given a Binary Tree, find the maximum sum path from a leaf to root.
For example, in the following tree, there are three leaf to root paths:
The sums of these three paths are 16, 4 and 17 respectively.
The maximum of them is 17 and the path for maximum is 7 -> 10.
10
/ \
-2 7
/ \
8 -4
Solution:
Here we provide a Java pseudo-implementation of the problem:
maxValue = 0
targetLeaf = null
maxLeafRootSum(root)
targetLeaf = findTargetLeaf(root, 0)
print(maxValue)
// set targetLeaf to the leaf with maximum sum path to root
findTargetLeaf(node, currMaxValue)
if root == null
return
// hold the sum of nodes on path from root to this node
currMaxValue += node.value
// leaf and the path to this has maximum sum: set targetLeaf
if node.isLeaf
if currMaxValue > maxValue
maxValue = currMaxValue
targetLeaf = node
// this is not a leaf node: recur down to find targetLeaf
findTargetLeaf(node.left, currMaxValue)
findTargetLeaf(node.right, currMaxValue)
So, the trivial solution of Maximum Path Sum works as follows:
For every node we call twice maxLeafRootSum, which costs O(n), hence the total cost is O(n^2)
We can find the maximum sum using single traversal of binary tree.
The idea is to maintain two values in recursive calls
For every visited node
As before, here a pseudo-code implementation:
maxValue = 0
// calculates two things:
// 1) maximum path sum between two leaves, which is stored in maxValue.
// 2) maximum root-to-leaf path sum, which is returned.
maxPathSum(root)
if root == null
return 0
left = maxPathSum(root.left)
right = maxPathSum(root.right)
maxValue = Math.max(maxValue, left + right + root.value)
return left + right + root.value
In "one pass" (aka one traversal) we do what we did in the trivial solution.
The reasoning is the following:
The result is maxValue when the program terminates.
This Problem is not mandatory: used to present the Two Pointers Trick.
Given a sorted array
The naive approach is obvious and takes O(n^2), we simply scan the array and we return when we find two numbers that adds up to X.
existsPairSum(a[], x)
n = a.length()
for i = 0 to n
for j = i+1 to n
if a[i] + a[j] == x
return true
if a[i] + a[j] > x
break // a is sorted, need a new "i"
return false
Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array.
It employs using two pointer, typically one from the start of the array going left-to-right and one from the end of the array going right-to-left, until they meet.
We already seen a sneak peak of this in Trapping Rain Water.
We take two pointers, one representing the first element and other representing the last element of the array, and then we add the values kept at both the pointers.
If their sum is smaller than X then we shift the left pointer to right or if their sum is greater than X then we shift the right pointer to left, in order to get closer to the sum.
We keep moving the pointers until we get the sum as X.
existsPairSum(a[], x)
n = a.length()
left = 0
right = n-1
while left < right
if a[left] + a[right] == x
return true
if a[left] + a[right] < x
left += 1 // smaller than target, we need to increase
else
right -= 1 // bigger than target, we need to decrease
return false
There are
For each frog two values
For each mosquito two values are known
Frogs and mosquitoes are represented as points on the coordinate axis.
The frog can eat mosquito if mosquito is in the same position with the frog or to the right, and the distance between them is not greater than the length of the tongue of the frog.
If at some moment several frogs can eat a mosquito the leftmost frog will eat it (with minimal
After eating a mosquito the length of the tongue of a frog increases with the value of the size of eaten mosquito.
It's possible that after it the frog will be able to eat some other mosquitoes (the frog should eat them in this case).
For each frog print two values - the number of eaten mosquitoes and the length of the tongue after landing all mosquitoes and after eating all possible mosquitoes by frogs.
Each mosquito is landing to the coordinate axis only after frogs eat all possible mosquitoes landed before.
Mosquitoes are given in order of their landing to the coordinate axis.
A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
The time complexity of operations on the binary search tree is linear with respect to the height of the tree.
Binary search trees allow binary search for fast lookup, addition, and removal of data items.
Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm.
The complexity analysis of BST shows that, on average, the insert, delete and search takes
In the worst case, they degrade to that of a singly linked list:
Searching for a specific key can be programmed recursively or iteratively.
Searching begins by examining the root node. If the tree is nil, the key being searched for does not exist in the tree.
Otherwise, if the key equals that of the root, the search is successful and the node is returned.
If the key is less than that of the root, the search proceeds by examining the left subtree. Similarly, if the key is greater than that of the root, the search proceeds by examining the right subtree.
This process is repeated until the key is found or the remaining subtree is nil.
If the searched key is not found after a nil subtree is reached, then the key is not present in the tree.
For certain operations, given a node
Assuming all the keys of the BST are distinct, the successor of a node
On the other hand, the predecessor of a node
Following is pseudo-code for finding the successor and predecessor of a node
We store the position of the frogs in a BST, frogBST.
When a mosquito lands on a position frogBST.predecessor(b) query on the tree.
It is possible that some mosquito cannot be eaten right away, the uneaten mosquito will be stored in their own BST (mosquitoBST), using their landing position as keys.
There is no need to sort anything.
The algorithm behaves as follows:
frogBST using their position as keym in mosquitoesf of m in frogBST, if f.position + f.tongue >= m.positionf eats the mosquito m and its tongue grows by the size of mf now can eat other mosquitoes that could not be eaten before, inspect mosquitoBST to see if there is a mosquito that f can eat, and in case repeat.m' of f.position in mosquitoBST and see if f.position + f.tongue >= m'.positionf now may overlap or fully contain other frogsf in frogBST:f remove the overlap by updating their positionsf.position + f.tongue + 1f then delete this frog as it will never eatm in mosquitoBST and continueTime Complexity:
Consider a set of
We say that two intervals
Compute the maximum number of overlapping intervals.
Example:
We have a set of 10 intervals, the maximum number of overlapping intervals is 5 (at positions 3 and 4)
The Sweep Line Algorithm is an algorithmic paradigm used to solve a lot of problems in computational geometry efficiently.
The sweep line algorithm can be used to solve problems on a line or on a plane.
The sweep and line algorithm use an imaginary vertical line sweeping over the x-axis.
As it progresses, we maintain a running solution to the problem at hand.
The solution is updated when the vertical line reaches a certain key points where some event happen. The type of the event tells us how to update the solution.
Let's apply the sweep and line algorithm to the problem above.
We let the sweep line from left to right and stop at the beginning or at the end of every interval.
These are the important points at which an event occurs: interval start or end.
We also maintain a counter which keeps track of the number of intervals that are currently intersecting the sweep line, along with the maximum value reached by the counter so far.
For each point we first add to the counter the number of intervals that begin at that point, and then we subtract the number of intervals that end at that point.
The figure below shows the points touched by the sweep line and the values of the counter:
Observation: The sweep line only touches points on the x-axis where an event occurs.
This is important because the number of considered points, and thus the time complexity, is proportional to the number of intervals, and not to the size of the x-axis.
The following is the intuitive solution.
It has two nested loops, one that iterates right-left times and the inner one that iterates
The complexity then is
isCovered(ranges, left, right)
for i = left to right
covered = false // i is not covered until proven otherwise
for range in ranges
if i >= range.start && i <= range.end
covered = true // i is covered by the current interval
break;
// if i is not covered then we return false
if covered == false
return false
// each i in [left, right] is covered by at least one range
return true;
To solve the problem more efficiently we use sweep line and a map.
The complexity is linear in the maximum between the number of ranges and right
isCovered(ranges, left, right)
// map: point i -> number of open ranges in i
HashMap openRangesAt;
for range in ranges
openRangesAt.insert(openRangesAt.getOrDefault(range.start, 0) + 1)
// range.end+1 as the ranges are inclusive!
openRangesAt.insert(openRangesAt.getOrDefault(range.end+1, 0) + 1)
openRangesNow = 0
for i = 0 to left
openRangesNow += openRangesNow.getOrDefault(i, 0)
for point=left to right
openRangesNow += openRangesNow.getOrDefault(point, 0)
if openRangesNow == false
return false
return true
The array
Let's call the sequence of one or more consecutive elements in
Also let's call the segment
Note: if the distance between two numbers is abs(1) then the two numbers are consecutive.
Find any longest k-good segment.
Note: we return the indexes of the longest k-good segment
We use the sliding window approach: the implementation is self-explanatory
longestKGoodSegment(array, k)
n = array.length()
if k == 0 || n == 0
return (-1,-1)
if k == 1
return (0,0)
wSize = 1 // current window size
left, right = 0 // left and right delimiter of the window
pointer = 1 // always points to the element just outside the window
maxWSize = 1 // store the maximum size of the window so far
leftResult, rightResult = 0 // delimiter of the maximum window
HashSet distincts // store distinct elements in the window
distincts.insert(array[0]) // the windows starts with the first element
while pointer != n // proceed until the pointer is outside the array
// the element just outside the window is to be included
if Math.abs(array[right], array[pointer]) == 1
distincts.insert(array[pointer]);
right ++ 1 // stretch the window
wSize ++ 1 // the size of the window grows
pointer ++ 1 // shift the pointer to be outside of the window
if wSize > maxWSize // the new size is the maximum?
maxWSize = wSize
leftResult = left
rightResult = right
if distincts.size() == k // the window contains k distinct?
return (leftResult, rightResult)
else
left = pointer // shift the window: the start becomes pointer
right = left // the window is made of one element
w_size = 1
pointer = right+1 // points to the element outside the window
distincts.clear() // reset the distinct elements in the window
return (-1,-1)
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
kNote that:
x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.The obvious brute force approach: from each element we compute every possible subarray starting in that element, check if sum is a multiple of k and store the maximum length so far.
Prefix sums, also known as cumulative sums or cumulative frequencies, offer an elegant and efficient way to solve a wide range of problems that involve querying cumulative information about a sequence of values or elements.
The essence of prefix sums lies in transforming a given array of values into another array, where each element at a given index represents the cumulative sum of all preceding elements in the original array.
An example of prefix sum array is shown in the picture:
Where it is clear that
We can use the combinator scan to produce the prefix sums from an iterator.
scan is an iterator adapter, it maintains an internal state, initially set to a seed value, which is modified by a closure taking both the current internal state and the current element from the iterator into account.
let a = vec![2, 4, 1, 7, 3, 0, 4, 2];
let psums = a
.iter()
.scan(0, |sum, e| {
*sum += e;
Some(*sum)
})
.collect::<Vec<_>>();
assert!(psums.eq(&vec![2, 6, 7, 14, 17, 17, 21, 23]));
The solution is based on the following mathematical property:
Observation: any two prefix sums that are not next to each other with the same mod k, or a prefix sum with mod k = 0 that is not the first number will yield a valid subarray.
checkSubarraySum(array, k)
n = array.length()
prefixSumArray[] // prefix sum array
pS = 0
for i = 0 to n
pS += array[i]
prefixSumArray[i] = pS
// map: modulo -> index i st prefixSumArray[i] % k = modulo
HashMap modsToIndices
for (i, prefixSum) in array.enumerate()
modulo = prefixSum % k
if modulo == 0 && i != 0 // if modulo is 0 and not the first ok
return true
// first time we see this modulo
if modsToIndices.contains(modulo) == false
modsToIndices.insert(modulo, i)
else
// this modulo has been seen
previousIndex = modsToIndices.get(modulo);
if previousIndex < i - 1
return true
return false
Observation:
We really do not need a full prefix sum array, it is enough to compute sum as we go and use it also as the mod result (we make sum = sum%k and use it as key, sums in modulo works). This is true because we never use the prefix sum of an element before the predecessor, so we can store only the sum up until now.
You have an array containing n elements initially all 0.
You need to do a number of update operations on it.
In each update you specify l, r and val which are the starting index, ending index and value to be added.
After each update, you add the val to all elements from index l to r.
After u updates are over, there will be q queries each containing an index for which you have to print the element at that index.
Observation: access(i) wants the prefix sum of the elements `A[1..i]
To efficiently solve this problem we introduce a new data structure, the Fenwick Tree
The Fenwick Tree, also known as the Binary Indexed Tree (BIT), is a data structure that maintains the prefix sums of a dynamic array.
With this data structure we can update values in the original array and still answer prefix sum queries.
Both operations runs in logarithmic time.
Consider the following problem: we have an array A[1..n] of integers and we would like to support the following operations:
sum(i) returns the sum of the elements in A[1...i]add(i,v) adds the value v to the entry A[i]We have two trivial solutions:
A as it is. This way, sum(i) is solved by scanning the array in add(i,v) is solved in A. This way sum(i) is solved in add(i,v) is solved modifying all the entries from i to n in The sum/add query time trade-offs of these solutions are unsatisfactory
The Fenwick Tree provides better tradeoffs for this problem.
The Fenwick tree efficiently handles these queries in
In fact the Fenwick tree is an implicit data structure, which means it requires only A
In our description, we will gradually introduce this data structure by constructing it level by level.
We use the following 1-indexed array in our example:
We start with a simpler version of the problem: we focus on solving sum queries only for positions that are powers of 2, positions 1, 2, 4, 8 in A.
The solution of this simplified version, shown in the picture, will be the first level of the Fenwick Tree
We notice that:
AWith this solution we have that:
sum(i) query: straightforward, we simply access the node i, provided that i is a power of 2add(i,v) query: we need to add v to all the nodes that covers ranges that include the position i, for example if we want to do add(3,10) we need to add 10 to the nodes 4 (as it has range add(i,v): find the smallest power of 2 grater than i, let's call it j, and we add v to the nodes j, j*2, j*(2^2), ... (j is the index in the original array, stored over every node in the picture above)We observe that sum takes constant time and add takes
This is very good, can we extend this solution to support sum queries on more positions?
Observation: currently we are not supporting queries for positions within the ranges between consecutive powers of 2.
Look at the image above: positions that falls in the range (subarray) [5, 7], which falls between the indices
In fact we can't make the query sum(5).
Enabling queries for this subarray is a smaller instance of our original problem.
We can apply the same strategy by adding a new level to our tree.
The children of a node stores the partial sums starting from the next element.
The emphasis is in starting.
If the subarray is A[l..r], the new level will support the sum(i) query for any i such that i-l+1 is a power of 2.
Lemma: our two-level tree can now handle sum(i) queries for positions that are the sum of two powers of 2.
Proof:
i expressed as i at the second levelsum(5)Which are the position still not supported? The positions that are neither a power of 2 or the sum of two powers of 2.
In our example, we can't compute sum(7) as 7 is either of those.
To support this we add a new level to our tree, so we can support positions that are sum of three powers of 2
Example: intuition on how to compute sum(7)
sum(7)And we are done, this is the Fenwick tree of the array A.
We can make some observations:
A because any of its entries A[i] can be simply obtained by doing sum(i) - sum(i-1). This is why the Fenwick tree is an implicit data structureNow, let’s delve into the details of how to solve our sum and add queries on a Fenwick tree.
sum queryThis query involves beginning at a node i and traversing up the tree to reach the node 0
Thus sum(i) takes time proportional to the height of the tree, resulting in a time complexity of
Let's consider the case sum(7) more carefully.
We start at node 7 and move to its parent (node 6), its grandparent (node 4), and stop at its great-grandparent (the dummy root 0), summing their values along the way.
This works because the ranges of these nodes (
Answering a sum query is straightforward if we are allowed to store the tree's structure.
However a significant part of the Fenwick tree's elegance lies in the fact that storing the tree is not actually necessary.
This is because we can efficiently navigate from a node to its parent using a few bit-tricks, which is the reason why the Fenwick trees are also called Binary Indexed Trees.
We want to compute the parent of a node, and we want to do it quickly and without representing the structure of the tree.
Let's consider the binary representation of the indexes involved in the query sum(7)
Theorem: the binary representation of a node's parent can be obtained by removing the trailing one (i.e., the rightmost bit set to 1) from the binary representation of the node itself.
addNow we consider the operation add(i,v).
We need to add the value v to each node whose range include the position i.
Surely, the node i itself is one of these nodes as its range ends in i.
Additionally, the right siblings of node i also encompasses the position i in their ranges.
This is because siblings share the same starting positions, and right siblings have increasing sizes.
The right siblings of the parent node of i, the right siblings of the grandparent, and so on can also contain position i.
It might seem like we have to modify a large number of nodes, however we can show that the number of nodes to be modified is at most log(n).
This is because each time we move from a node to its right sibling or to the right sibling of its parent, the size of the covered range at least doubles. And a range cannot double more than \log(n) times.
If we want to perform add(5, x) we just need to modify the nodes in red:
We now know which are the nodes to modify for add(i, x).
Let's discuss how to compute these nodes with bit-tricks.
Continuing the above example, starting with i = 5, the next node to modify is its right sibling, node 6.
Their binary representation is
We see that if we isolate the trailing one in the binary rep. of 5, which is 0001, and add it to the binary rep. of 5 itself, we obtain the binary rep of 6.
Finding the Sibling
The binary representation of a node and its sibling matches, except for the position of the trailing one. When we move from a node to its right sibling, this trailing one shifts one position to the left.
Adding this trailing one to a node accomplishes the required shift.
Now, consider the ID of a node that is the last child of its parent.
In this case, the rightmost and second trailing one are adjacent. To obtain the right sibling of its parent, we need to remove the trailing one and shift the second trailing one one position to the left.
Thankfully, this effect is one again achieved by adding the trailing one to the node’s ID.
The time complexity of add is
The following is a minimal implementation.
While we’ve transitioned to 0-based indexing for queries, internally, we still use the 1-based indexing to maintain consistency with the examples above.
#[derive(Debug)]
pub struct FenwickTree {
tree: Vec<i64>,
}
impl FenwickTree {
pub fn with_len(n: usize) -> Self {
Self {
tree: vec![0; n + 1],
}
}
pub fn len(&self) -> usize {
self.tree.len() - 1
}
/// Indexing is 0-based, even if internally we use 1-based indexing
pub fn add(&mut self, i: usize, delta: i64) {
let mut i = i + 1;
assert!(i < self.tree.len());
while i < self.tree.len() {
self.tree[i] += delta;
i = Self::next_sibling(i);
}
}
/// Indexing is 0-based, even if internally we use 1-based indexing
pub fn sum(&self, i: usize) -> i64 {
let mut i = i + 1;
assert!(i < self.tree.len());
let mut sum = 0;
while i != 0 {
sum += self.tree[i];
i = Self::parent(i);
}
sum
}
pub fn range_sum(&self, l: usize, r: usize) -> i64 {
self.sum(r) - if l == 0 { 0 } else { self.sum(l - 1) }
}
fn isolate_trailing_one(i: usize) -> usize {
if i == 0 {
0
} else {
1 << i.trailing_zeros()
}
}
fn parent(i: usize) -> usize {
i - Self::isolate_trailing_one(i)
}
fn next_sibling(i: usize) -> usize {
i + Self::isolate_trailing_one(i)
}
}
We are given an array A[1,n] initially set to 0.
We want to support two operations:
access(i) returns A[i]range_update(l, r, v), updates the entries in A[l,r] adding to them vThe following Fenwick solution solve the problem on an array B[1,n].
B we build the Fenwick Tree of length n (mind that B is initialized with all zeros)access(i) is a wrapper of the operation sum(i) we have seen beforerange_update(l,r,v) exploit the operation add(i, v) of the implementation of the Fenwick Tree:l is <= than r, aka that the interval of entries to update is well formedr <= n, aka that the interval of entries to update is actually in the arrayadd(l,v): this trigger the addition of the value v to each node whose range include the position l in the Fenwick Treeadd(r, -v): this trigger the subtraction of the value v to each node whose range include the position r in the Fenwick Treev in the Fenwick tree, this means that prefix sum are coherent and the elements in [l,r] are increased by v#[derive(Debug)]
struct UpdateArray {
ft: FenwickTree,
}
impl UpdateArray {
pub fn with_len(n: usize) -> Self {
Self {
ft: FenwickTree::with_len(n),
}
}
pub fn len(&self) -> usize {
self.ft.len()
}
pub fn access(&self, i: usize) -> i64 {
self.ft.sum(i)
}
pub fn range_update(&mut self, l: usize, r: usize, v: i64) {
assert!(l <= r);
assert!(r < self.ft.len());
self.ft.add(l, v);
if r + 1 < self.ft.len() {
self.ft.add(r + 1, -v);
}
}
}
We are given
There are no coinciding endpoints among the segments.
The task is to determine and report the number of other segments each segment contains.
Alternatively said: for the segment
We provide two solutions to this problem:
We use a sweep line & Fenwick tree approach.
For starters we map the segments to the range
Then we build the Fenwick tree, we scan each segment
Now we scan the segments again.
When we process the segment
Now to find the solution of this problem for the current segment (aka the number of segments contained in the current one) we need to know the number of these segments (the ones that starts before the current one) that also end before the current one, before
This is computed with a query sum(r_i) on the Fenwick Tree.
After computing the solution for the current segment we subtract
The following snippet implement the solution above, using the Fenwick tree previously defined.
fn fenwick_nested_segments(input_segments: &[(i32, i32)]) -> Vec<(i64, usize)> {
let n = input_segments.len();
// (start, end, index_in_input)
let mut events: Vec<(i32, i32, usize)> = Vec::with_capacity(n);
for (i, &(l, r)) in input_segments.iter().enumerate() {
events.push((l, r, i));
}
// sort by starting endpoint
events.sort_by(|a, b| a.0.cmp(&b.0));
let mut tree = FenwickTree::with_len(input_segments.len()*2 + 1);
for i in 0..n {
tree.add(events[i].1 as usize, 1);
}
let mut sol: Vec<(i64, usize)> = Vec::with_capacity(n);
for i in 0..n {
sol.push((tree.sum(events[i].1 as usize) - 1, events[i].2));
tree.add(events[i].1 as usize, -1);
}
// restore so that the solution are paired with the input ordering
sol.sort_by(|a, b| a.1.cmp(&b.1));
sol
}
A Segment Tree is a data structure that stores information about array intervals as a tree.
This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array.
The key point here is range queries, not only range sums!
We can find the sum of consecutive array elementsA[l..r] or find the minimum element in a segment in
Between answering such queries we can modifying the elements by replacing one element of the array, or even changing the elements of a whole subsegment (e.g., assigning all elements a[l..r] to any value, or adding a value to all element in the subsegment)
Segment trees can be generalized to larger dimensions. For instance, with 2-dimensional Segment trees you can answer sum or minimum queries over some subrectangle of a given matrix in
We consider the simplest form of Segment Trees.
We want to answer sum queries efficiently.
The formal definition of our task is the following: given an array
Observation: even our simple form of Segment Tree is an improvement over the simpler approaches:
We can take a divide-and-conquer approach when it comes to array segments.
We compute and store the sum of the elements of the whole array, i.e. the sum of the segment
Then we split the array into two halves
We can view this segment as forming a binary tree: the root is the whole array segment, and each vertex (except leaves) has exactly two children.
This is why this data structure is called "segment tree".
Example: consider the array
From the short description we just gave we can conclude that Segment Trees only require a linear number of vertices.
The first level of our tree contains a single node (the root), the second level will contain two nodes, the third we have four nodes, until the reaches
Thus, the number of vertices in the worst case can be estimated by the sum
The height of a Segment Tree is
Before constructing the segment tree we need to decide:
Note that a vertex is a leaf if its corresponding segment covers only one value of the original array. It is present at the lowest level of the tree and its value would be equal to the corresponding element
For construction of the segment tree, we start at the bottom level (the leaves) and assign them their respective values.
On the basis of these values we can compute the values of the previous level, using the merge function.
And on the basis of those, we can compute the values of the previous, and so on until we reach the root.
It is convenient to describe this operation recursively in the other direction, i.e., from the root vertex to the leaf vertices.
The construction procedure, if called of a non-leaf vertex, does the following:
We start the construction at the root vertex, and hence, we are able to compute the entire segment tree.
The time complexity of the construction is
We receive two integers
To do this we will traverse the tree and use the precomputed sums of the segments.
Let's assume that we are currently at the vertex that covers the segment
There are three possible cases:
So processing a sum query is a function that recursively calls itself once with either the left or the right child (without changing the query boundaries), or twice, once for the left and once for the right child (by splitting the query into two subqueries).
And the recursion ends whenever the boundaries of the current query segment coincides with the boundaries of the segment of the current vertex.
In that case the answer will be the precomputed value of the sum of this segment, which is stored in the tree.
Obviously we will start the traversal from the root vertex of the Segment Tree.
Example: consider the array
Let's now reason about the complexity of the algorithm.
We have to show that we can compute the sum queries in
Theorem: for each level we only visit no more than four vertices.
And since the height of the tree is
Now we want to modify a specific element in the array, let's say we want to do the assignment
This query is easier than the sum query. Each level of a segment tree forms a partition of the array. Therefore an element
Thus only
It is easy to see that the update request can be implemented using a recursive function. The function gets passed the current tree vertex, and it recursively calls itself with one of the two child vertices (the one that contains
Example: given the same array as before, we want to perform the update
Segment Trees allows applying modification queries to an entire segment of contiguous elements and perform the query in the same time
When we need to update an interval we will update a node and mark its child that it needs to be updated and update it only when needed.
To every node we add a field that marks if the current node has a pending update or not.
Then, when we perform another range update or a sum query, if nodes with a pending update are involved, we first perform the updates and then solve the query.
Alternatively said, consider the following segment tree:
When there are many updates and updates are done on a range, we can postpone some updates (avoid recursive calls in update) and do those updates only when required.
Please remember that a node in segment tree stores or represents result of a query for a range of indexes.
And if this node’s range lies within the update operation range, then all descendants of the node must also be updated.
Example: consider the node with value
If our update query is for range
With Lazy propagation, we update only node with value lazy[] which represents lazy node.
The size of lazy[] is same as array that represents segment tree.
The idea is to initialize all elements of lazy[] as 0. A value 0 in lazy[i] indicates that there are no pending updates on node i in segment tree.
A non-zero value of lazy[i] means that this amount needs to be added to node i in segment tree before making any query to the node.
Let's now solve nested segments with a Segment Tree and Sweep Line
Given the input array segments we compute the maximum endpoint between the segments, and call it n.
Then we create a segment tree, based on an array of length
At this point we create the array axis, which stores triples where:
segmentsisStart, which is set to true if the endpoint is the start of its segment, otherwise the end.We sort axis by the first element, the segments endpoints.
Finally we "sweep" over axis.
for `i = 0 to axis.length()axis[i].isStart == false, aka if the current endpoint is the end of its segmentaxis[i].endpoint, that we call res, is the range sum on the range [segments[axis[i].index, axis[i].endpoint(axis[i].index, res) in the array of resultsaxis[i].index in segmentsresults by the indexes and return itWhy it works?
In words:
Consider the segments
When we find the end of a segment
Then we increase by
This works because we increase by one the start
The range sum on
Alternatively said:
An array of positive integers
Let us consider its arbitrary subarray
For every positive integer
We call the power of the subarray the sum of products
The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.
You should calculate the power of
Besides the trivial solutions, we introduce a new algorithmic technique.
The Mo’s Algorithm is a powerful and efficient technique for solving a wide variety of range query problems.
It becomes particularly useful for kind of queries where the use of a Segment Tree or similar data structures are not feasible.
This typically occurs when the query is non-associative, meaning that the result of a query on a range cannot be derived by combining the answers of the subranges that cover the original range.
Mo’s algorithm typically achieves a time complexity of
Let's consider an easier problem than Powerful Array
We are given an array
Additionally we are given a set of three_or_more.
The query three_or_more(l,r) aims to count the colors that occur at least three times in the subarray
A straightforward solution for the problem: simply scan the subarray and use an additional array as a counter to keep track of occurrences of each color within the range.
Whenever a color reaches three the answer is incremented by 1.
Mind that after each query we have to reset the array of counters.
Indeed, it’s evident that it has a time complexity of
The figure below illustrates an input that showcases the worst-case running time.
We have
The total length of these ranges is
Let's now see the solution using the Mo's Algorithm.
Suppose we have just answered the query for the range
Instead of starting from scratch, we can update the previous answer and counters by adding or removing the contributions of colors that are new in the query range but not in the previous one, or vice versa.
Specifically, for left endpoints, we must remove all the colors in
The rust implementation below uses two closures, add and remove to keep answer and counters updated as we adjust the endpoints
pub fn three_or_more(a: &[usize], queries: &[(usize, usize)]) -> Vec<usize> {
let mut counters: Vec<usize> = vec![0; a.len()];
let mut answers = Vec::with_capacity(queries.len());
let mut cur_l = 0;
let mut cur_r = 0; // here right endpoint is excluded
let mut answer = 0;
for &(l, r) in queries {
let mut add = |i| {
counters[a[i]] += 1;
if counters[a[i]] == 3 {
answer += 1
}
};
while cur_l > l {
cur_l -= 1;
add(cur_l);
}
while cur_r <= r {
add(cur_r);
cur_r += 1;
}
let mut remove = |i| {
counters[a[i]] -= 1;
if counters[a[i]] == 2 {
answer -= 1
}
};
while cur_l < l {
remove(cur_l);
cur_l += 1;
}
while cur_r > r + 1 {
cur_r -= 1;
remove(cur_r);
}
answers.push(answer);
}
answers
}
The time complexity of the algorithm remains
However we observe that a query now executes more quickly if its range significantly overlaps with the range of the previous query.
This implementation is highly sensitive to the ordering of the queries.
The previous figure becomes now a best-case for the new implementation as it takes
Mind that it is enough to modify the ordering of the above queries to revert to quadratic time (alternate between very short and very long queries).
The above considerations lead to a question: if we have a sufficient number of queries, can we rearrange them in a way that exploits the overlap between successive queries to gain an asymptotic advantage in the overall running time?
Mo's Algorithm answers positively to this question by providing a reordering of the queries such that the time complexity is reduces to
The idea is to conceptually partition the array
A query belongs to a bucket
Initially we group the queries based on their corresponding buckets, and within each bucket the queries are solved in ascending order of their right endpoints.
The figure shows this bucketing approach and the queries of one bucket sorted by their right endpoint.
Let's analyze the complexity of the solution using this ordering
It is sufficient to count the number of times we move the indexes cur_l and cur_r. This is because both add and remove take constant time, and thus the time complexity is proportional to the overall number of moves of these two indexes.
Let's concentrate on a specific bucket. As we process the queries in ascending order of their right endpoints, the index cur_r moves a total of at most
On the other hand, the index cur_l can both increase and decrease but it is limited within the bucket, and thus it cannot move more than
Thus, for a bucket with
Summing up over all buckets the time complexity is
Here's a Rust implementation of the reordering process.
We sort the queries by buckets, using their left endpoints, and within the same bucket we sort them in ascending order by their right endpoints.
We also have to compute a permutation to keep track of how the queries have been reordered. This permutation is essential for returning the answers to their original ordering.
pub fn mos(a: &[usize], queries: &[(usize, usize)]) -> Vec<usize> {
// Sort the queries by bucket, get the permutation induced by this sorting.
// The latter is needed to permute the answers to the original ordering
let mut sorted_queries: Vec<_> = queries.iter().cloned().collect();
let mut permutation: Vec<usize> = (0..queries.len()).collect();
let sqrt_n = (a.len() as f64) as usize + 1;
sorted_queries.sort_by_key(|&(l, r)| (l / sqrt_n, r));
permutation.sort_by_key(|&i| (queries[i].0 / sqrt_n, queries[i].1));
let answers = three_or_more(a, &sorted_queries);
let mut permuted_answers = vec![0; answers.len()];
for (i, answer) in permutation.into_iter().zip(answers) {
permuted_answers[i] = answer;
}
permuted_answers
}
Final Considerations on Mo's Algorithm
Mo’s algorithm is an offline approach, which means we cannot use it when we are constrained to a specific order of queries or when update operations are involved.
When implementing Mo’s algorithm, the most challenging aspect is implementing the functions add and remove.
There are query types for which these operations are not as straightforward as in previous problems and require the use of more advanced data structures than just an array of counters
We can just use Mo's Algorithm and a little bit of attention in updating the answer after a add or a remove.
The solution is identical to the one seen in the previous problem, with one difference.
We are not interested anymore in the number of occurrences of
Code talks more than words:
let mut add = |i| {
// we found another occurrence of i, we remove the old "power"
sum -= counters[a[i]] * counters[a[i]] * a[i];
counters[a[i]] += 1;
// we update the power using the right number of occurreces of i
sum += counters[a[i]] * counters[a[i]] * a[i];
};
let mut remove = |i| {
sum -= counters[a[i]] * counters[a[i]] * a[i];
counters[a[i]] -= 1;
sum += counters[a[i]] * counters[a[i]] * a[i];
};
Given two strings, S1 and S2, the task is to find the length of the longest common subsequence, i.e. longest subsequence present in both strings.
Observation: subsequence != substring. A subsequence do not have to be contiguous.
There are many ways to attack this problem, we use it to talk about Dynamic Programming.
Dynamic Programming, like divide-and-conquer, solves problems by combining solutions of subproblems.
Divide-and-Conquer algorithms partitions the problem into disjoint subproblems, solve the subproblems and then combine their solutions to solve the original problem.
In contrast, dynamic programming applies when subproblems overlap, that is, when sub-problems share sub-sub-problems.
In this context a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common sub-sub-problems.
A dynamic programming algorithm solves each sub-sub-problem just once and then saves its answer in a table, avoiding the work of recomputing the answer every time it solves each sub-sub-problem.
Fibonacci numbers are defined as
Our goal is to compute the n-th Fibonacci number
Let's consider the following trivial recursive algorithm:
fibonacci(n)
if (n == 0)
return 0
if (n == 1)
return 1
return fibonacci(n-1) + fibonacci(n-2)
In computing fibonacci(n-1) we will compute fibonacci(n-2) and fibonacci(n-3),
and in computing fibonacci(n-2) we will compute fibonacci(n-3) and fibonacci(n-4) and so on.
There are lots of the same Fibonacci numbers that are computed every time from scratch.
Memorization is a trick that allows to reduce the time complexity.
Whenever we compute a Fibonacci number we store it in an array M.
Every time we need a Fibonacci number, we compute it only if the answer is not in the array.
This algorithm requires linear time and space.
fibonacciDP(n)
if (n == 0)
return 0
if (n == 1)
return 1
if (M[n] == null)
M[n] = fibonacciM(n-1) + fibonacciM(n-2)
return M[n]
There is a more direct bottom-up approach which uses linear time and constant space.
This approach typically depends on some natural notion of "size" of a sub-problem, such that solving any particular sub-problem depends only on solving "smaller" sub-problems.
We solve the subproblems by size and solve them in size order, smallest first.
When solving a particular sub-problem, we have already solved all the smaller subproblems its solution depends upon, and we have saved their solution.
In our case this approach corresponds to compute an array F which entry F[i] requires only on entries F[i-1] and F[i-2.
iteFibonacci(n)
F[n]
F[0] = 0
F[1] = 1
for i = 2 to n
F[i] = F[i-1] + F[i-2]
return F[n-1]
Tabulation and Memorization are two common techniques used in dynamic programming to optimize the solution of problems by avoiding redundant computations and storing intermediate results.
In summary, both tabulation and memorization are techniques used to optimize dynamic programming solutions by avoiding redundant computations.
Tabulation builds a table bottom-up, while memorization caches results top-down.
Now that we have refreshed dynamic programming we can go back to our problem.
The subproblems here ask to compute the longest common subsequence (LCS) of prefixes of the two sequences S1 and S2: given two prefixes S1[1,i] and S[1,j] our goal is to compute LCS(S1[1,i], S2[1,j])
Assume that we already know the solutions to the following three smaller problems
LCS(S1[1,i-1], S2[1,j-1])LCS(S1[1,i], S2[1,j-1])LCS(S1[1,i-1], S2[1,j])Then we have that
S1[i] == S2[j] we can extend a LCS of S1[1,i-1] and S2[1,j-1] by adding one character c = S1[i]S1[i] != S2[j] we can only consider LCS(S1[1,i], S2[1, j-1]) and LCS(S1[1,i-1], S2[1,j]), and we take the longer.Summarizing:
The pseudo-code of the problem is the following
longestCommonSubsequence(x, y)
n = x.length() + 1
m = y.length() + 1
dp = [n][m]
// the first row and the first column are initialized to 0
// represent the length 0 of the first or second string
for i = 0 to n
dp[i][0] = 0
for j = 0 to m
dp[0][j] = 0
for i = 1 to n
for j = 1 to m
if x[i] == y[j]
dp[i][j] = dp[i-1][j-1] + 1
else
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return C[n-1][m-1]
Consider an array of N integers arr[].
Each element represents the maximum length of the jump that can be made forward from that element.
This means if arr[i] = x, then we can jump any distance y such that y <= x.
Find the minimum number of jumps to reach the end of the array starting from the first element.
If an element is 0, then you cannot move through that element.
Note: Return -1 if you can't reach the end of the array.
We use Dynamic Programming to solve the problem.
More specifically we use Tabulation to solve the problem:
jumps[] from left to right such that jumps[i] indicate the minimum number of jumps needed to reach the position i starting from the startjumps[]. we use two nested loops, the outer indexed with i and the inner indexed with ji = 1 to n-1 and the inner loop goes from j = 0 to ii is less than j+arr[j] then sets jumps[i] to min(jumps[i], jumps[j]+1jump[i] = INT_MAXjumps[i-1]The implementation of the solution is the following:
minNumberOfJumps(array)
n = array.le
jumps[n]
for i = 0 to n
jumps[i] = MAX
jumps[0] = 0
if n == 0 || arr[0] == 0
return -1
for i = 1 to n
for j = 0 to i
// read below
if i <= j + array[j] && jumps[j] != MAX
jumps[i] = Math.min(jumps[i], jumps[j]+1)
break
return jumps[n-1]
}
The key is the if guard inside the two loops:
i <= j + arr[j]: we want to reach i and we are in j. If i <= j + array[j] it means that i is reachable from j doing the available number of jumps in j, which are array[jjumps[j] != MAX: we can actually reach j from the startThen the minimum number of jumps required to reach i is the minimum between the current number of jumps to reach i and the number of jumps required to reach j plus one more jump (to reach i)
Given an array array[] of size N, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.
This problem is a well-known NP-Hard problem, which admits a pseudo-polynomial time algorithm.
The problem has a solution which is almost the same as 0/1 Knapsack Problem.
0/1 Knapsack Problem
We are given
It is called 0/1 because each item is either selected or not selected.
We can use the following solutions:
Weight Dynamic Programming
The idea is to fill a
Let
Profit Dynamic Programming
The idea is similar.
We can use a
Let
Thus we have:
As in the 0/1 knapsack problem we construct a matrix
Here the matrix contains booleans.
The entry true if and only if there exists a subset of the first
The entries of the first row
The entries of the first column
Entry
Said easy:
partialEqualSubsetSum(array)
n = array.length()
sum = 0
for i = 0 to n
sum += array[i]
if sum % 2 != 0
return false
sum = sum / 2
// dp[i][j] = true if exists a subset of the
// first i elements in array that summed gives j
dp[n+1][sum+1]
for i = 0 to n+1
dp[i][0] = true
for j = 1 to sum+1
dp[0][j] = false
// i is the current number of elements of which we make a subset
for i = 1 to n+1
// j is the current "target" sum
for j = 1 to sum+1
// if array[i-1] is alone bigger than j then it cannot be in
// the subset of elements that summed gives j
if array[i-1] > j
dp[i][j] = dp[i - 1][j]
else
dp[i][j] =
dp[i-1][j] || // dont put i in the subset
dp[i-1][j - array[i - 1]] // put i in the subset
return dp[n][sum]
The then branch of the if is crucial: if arr[i - 1] is greater than j, it means that including the current element i in the subset would make the sum exceed the current target sum j.
Therefore, the solution at dp[i][j] would be the same as the solution without including the current element, i.e., sol[i - 1][j] (aka, we do not include i, as we can't)
Given an array of integers, find the length of the longest (strictly) increasing subsequence
from the given array.
observation: subsequence, as before, it is not a contiguous.
As an example consider the sequence
The length of
In general the
Consider the sequence
Due to optimal substructure and overlapping subproblem property, we can also utilize Dynamic programming to solve the problem. Instead of memoization, we can use the nested loop to implement the recursive relation.
The outer loop will run from i = 1 to N and the inner loop will run from j = 0 to i and use the recurrence relation to solve the problem.
The reasoning is the following:
for i in 1..n) iterates over each element of the array starting from the second element.for j in 0..i) iterates over elements before the current element arr[i].arr[i] is greater than the element at index j and if increasing the length by 1 (lis[j] + 1) results in a longer LIS ending at index i. If true, it updates lis[i] accordingly.longestIncreasingSubsequence(array)
n = array.length()
lis[n]
for i = 0 to n
lis[i] = 1
for i = 1 to n
// j is used to compute the LIS of the prefix up to i
for j = 0 to i
// if the current element is bigger than the previous element
// array[j] and the lis[i] is smaller than lis[j] plus the
// current element
if array[i] > array[j] && lis[i] < lis[j] + 1
lis[i] = lis[j] + 1
return lis.max()
The main idea of the approach is to simulate the process of finding a subsequence by maintaining a list of “buckets” where each bucket represents a valid subsequence.
Initially, we start with an empty list and iterate through the input nums vector from left to right.
For each number in nums
Consider the following pseudo-implementation
smartLIS(nums)
n = nums.length()
List ans
ans.add(nums[0])
for i = 1 to n
if nums[i] > ans.last()
ans.add(nums[i])
else
// low is the index of the smallest element >= nums[i] in `ans`
low = binarySearch(ans, nums[i])
ans.set(low, nums[i]);
return ans.length()
theory_TODO
Given an array arr[0 … n-1] containing arr[] is called bitonic if it is first increasing, then decreasing.
Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.
A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.
This problem is a slight variation of the previous problem.
Let the input array arr[] be of length n.
We need to construct two arrays lis[] and lds[] using the DP solution of the Longest Increasing Subsequence
lis[i] stores the length of the longest increasing subsequence ending in arr[i]lds[i] stores the length of the longest decreasing subsequence starting in arr[i]We return the max value of lis[i] + lds[i] -1 where
To compute lds[i] we iterate through the array backwards and apply the same reasoning used for lis[], as we are looking for a decreasing sequence but proceeding backwards, is the same as an increasing sequence.
Basically the output is the sum of the longest increasing sequence left to right and the longest increasing sequence right to left
The following is the implementation of the solution:
longestBitonicSubsequence(array)
n = array.length()
// exactly as LIS
lis[n]
for i = 0 to n
lis[i] = 1
for i = 1 to n
for j = 0 to i
if array[i] > array[j] && lis[i] < lis[j] + 1
lis[i] = lis[j] + 1
// LIS but backwards
lds[n]
for i = 0 to n
lds[i] = 1
for i = n-1 to 0
for j = n-1 to i
if array[i] > array[j] && lds[i] < lds[j] + 1 {
lds[i] = lds[j] + 1
}
lisMax = lis.max()
ldsMax = lds.max()
return lisMax + ldsMax - 1
There is one meeting room in a firm.
There are N meetings in the form of (start[i], end[i]) where start[i] is start time of meeting i and end[i] is finish time of meeting i.
Find the maximum number of meetings that can be accommodated in the meeting room, knowing that only one meeting can be held in the meeting room at a particular time.
Note: Start time of one chosen meeting can't be equal to the end time of the other chosen meeting.
There are various ways to solve the problem, we use it to present greedy algorithms.
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.
In many problems a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.
Example: a greedy strategy for the Travelling Salesman Problem (TSP) is the heuristic "at each step of the journey visit the nearest city".
This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps.
Note: this greedy approach is not very good on the TSP, as the current optimal choice is based on previous choices, and greedy algorithms never reconsider the choices they have made so far.
Most problems for which greedy algorithms yields good solutions (aka good approximation of the globally optimal solution) have two property:
We use the greedy approach to solve the problem:
results of meetings and set a variable time_limit to the finish time of the first meetingresultstime_limit variable to the finishing time of the current meetingObservation: the problem requires only to give the maximum number of meetings that we can have in one room.
We do not care about the meetings that can be held, so results is useless.
Also we can sort the array of meetings that we have received, as there is no problem in messing their order.
In the end, we need only the variable time_limit and a variable result to increment every time we find a meeting that can happen.
The following implementation solves the problem:
meetingsInARoom(meetings)
// sort meetings by their starting time
meetings.sort()
timeLimit = meetings[0].end
// at least we held the first meeting
result = 1
for meeting in meetings
if meeting.0 > timeLimit
result++
timeLimit = meeting.end
return result;
Wilbur the pig is tinkering with arrays again.
He has the array
At one step he can choose any index
His goal is to end up with the array
Of course Wilbur wants to achieve this goal in the minimum number of steps and asks you to compute this value.
Example:
= [0,0,0,0,0][1,2,3,4,5], the target array +1 operation, one for every element ii = 0: +1 a = [1,1,1,1,1]i = 1: +1 a = [1,2,2,2,2]The solution is based upon the observation that the minimum number of operations is equal to the sum of differences (in absolute value) between consecutive elements.
Given the array
Here's the rust implementation:
wilburAndArray(array)
n = array.length()
result = Math.abs(array[0])
for i = 1 to n
result += Math.abs(array[i] - array[i-1])
return result
Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood.
She imagined the situation that is described below.
There are
Each tree has its height
Woodcutters can cut a tree and fell it to the left or to the right.
After that it occupies one of the segments
The tree trait that is not cut down occupies a single point with coordinate
Woodcutters can fell a tree if the segment to be occupied by the fallen tree does not contain any occupied point.
The woodcutters want to process as many trees as possible.
What is the maximum number of trees to fell?
We use a greedy approach to solve the problem.
The code makes it even more clear:
woodcutters(trees)
n = trees.length()
// always cut at least the first and last trees
cutted = 2
for i = 1 to n-1
// left fall: the previous tree is placed before where the
// current trees fall when "left-cutted"
if trees[i-1].x < trees[i].x - trees[i].h
cutted++
continue
// cant fall to the left, lets try to the right
// if the current tree fall in a place that is smaller
// than the next tree place, then we cut
if trees[i].x trees[i].h < trees[i+1].x
cutted++
continue
return result
}
You are given an adjacency list of a graph adj of V of vertices having 0 based index. Check whether the graph is bipartite or not.
The Problem in detail:
A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
In other words, for every edge
We can also say that there is no edge that connects vertices of same set.
A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.
theory_TODO
We use the Breadth-First Search (BFS) to solve the problem:
red to the source vertexblue all the neighborsred all neighbor's neighborisBipartite(graph[][])
nNodes = graph.length()
// maps node i to the color of i
HashMap colors
for i = 0 to nNodes
// if the node i has not yet a node
if colors.containsKey(i) == false
// assign a color to i, if i has a neighbor
// of the same color then we return false
if colorBFS(graph, i, colors) == false
return false
return true
// returns true if a color was correctly assigned
// returns false if it finds a neighbor of node with the same color
colorBFS(graph[][], node, colors)
nNodes = graph.length()
// color the node
color.insert(node, 1)
// create the frontier
queue = new Queue()
queue.add(node)
while queue.isEmpty() == false
currentNode = queue.poll()
// iterate all the nodes
for i = 0 to nNodes
// currentNode and the node `i` are connected: i is a neighbor
if graph[node][i] == 1
// the neighbor i has an assinged color
if colors.containsKey(i) == true
// has the neighbor the same color as the current node?
if colors.get(i) == color.get(currentNode)
return false // the graph is not bipartite
else
// assign a different color to the neighbor
colors.add(i, 1 - colors.get(currentNode));
return true